package com.guet.DataStructures.stack;

import java.util.Scanner;

/**
 * @author MicahYin
 * @date 2020/11/10 20:44
 * 利用链表来实现栈
 */
public class LinkListStackDemo {
    public static void main(String[] args) {
        //测试创建的ArrayStack是否正确
        SingleLinkList singleLinkList = new SingleLinkList();
        String key="";
        boolean loop=true;
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("show:表示显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加数据到栈（入栈）");
            System.out.println("pop:表示从栈取出数据（出栈）");
            System.out.println("请输入你的选择");
            key=scanner.next();
            switch (key){
                case "show":
                    singleLinkList.show();
                    break;
                case "exit":
                    scanner.close();
                    loop=false;
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value=scanner.nextInt();
                    singleLinkList.push(value);
                    break;
                case "pop":
                    try {
                        int res = singleLinkList.pop();
                        System.out.printf("出栈的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("bye~~");
    }
}
//定义SingleLinkedList管理我们的英雄
class SingleLinkList{
    //初始化头结点----头结点很关键，不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0);
    /**
     * 添加节点到单向链表，即 push
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的next指向新的节点
     */
    public void push(int value){
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后的节点
        while (temp.next!=null){
            temp = temp.next;
        }
        //当while循环结束时，temp就指向了链表的最后
        temp.next = new HeroNode(value);
    }
    /**
     * 删除节点
     * 思路：
     * 1.head不能动。需要辅助节点temp，找到待删除节点的前一个节点
     * 2.temp.next = temp.next.next
     * @param no
     */
    public void del(int no){
        HeroNode temp = head;
        //是否找到该节点
        boolean flag = true;
        while (true){
            if (temp.next==null){
                flag=false;
                break;
            }else if (temp.next.no==no){
                //找到该节点的前一个节点，跳出
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("未找到%d节点",no);
        }
    }
    /**
     * 遍历显示链表中的元素
     */
    public void show(){
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，因此需要一个辅助变量来遍历
        HeroNode temp=head;
        while (temp.next!=null){
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 判断栈是否为null
     * @return 栈状态
     */
    public boolean isEmpty(){
        return head.next==null;
    }
    /**
     * 删除节点
     * 思路：
     * 1.head不能动。需要辅助节点temp，找到待删除节点的前一个节点
     * 2.temp.next = temp.next.nex
     */
    public int pop(){
        if (isEmpty()){
            //抛出异常
            throw new RuntimeException("栈空，没有数据~");
        }
        HeroNode temp = head;
        while (temp.next!=null){
            temp = temp.next;
        }
        //当while循环结束时，temp就指向了链表的最后
        int value = temp.no;
        del(value);
        return value;
    }
}
/**
 * 定义HeroNode,每个HeroNode对象就是一个节点
 */
class HeroNode{
    public int no;
    public HeroNode next;
    //构造函数
    public HeroNode(int no){
        this.no=no;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                '}';
    }
}